'''
https://leetcode.cn/problems/strange-printer/description/
'''
from functools import cache

INF = 2 << 32 - 1

class Solution:
    def strangePrinter(self, s: str) -> int:
        n = len(s)
        @cache
        def f(i, j):
            if i == j:
                return 1
            res = INF
            if s[i] == s[j]:
                res = min(res, f(i, j - 1))
            for m in range(i, j):
                res = min(res, f(i, m) + f(m+1, j))
            return res
        return f(0, n - 1)

    def strangePrinter2(self, s: str) -> int:
        n = len(s)
        dp = [[0] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = 1
        for i in range(n - 2, -1, -1):
            for j in range(i + 1, n):
                res = INF
                if s[i] == s[j]:
                    res = min(res, dp[i][j - 1])
                for m in range(i, j):
                    res = min(res, dp[i][m] + dp[m + 1][j])
                dp[i][j] = res
        return dp[0][-1]


s = 'aaabbb'
print(Solution().strangePrinter2(s))